package org.example.likou150.tree;

import com.sun.source.tree.Tree;

import java.util.ArrayList;
import java.util.List;

public class LowestCommonAncestor {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);

        LowestCommonAncestor lowestCommonAncestor = new LowestCommonAncestor();
        lowestCommonAncestor.lowestCommonAncestor(root, new TreeNode(1), new TreeNode(2));
    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p ||  root==q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left!=null && right!=null){
            return root;
        }
        return left!=null?left:right;
    }






//    List<TreeNode> list = new ArrayList<>();
//    int pIndex = 0;
//    int qIndex = 0;
//    int index = 0;
//    private TreeNode resultNode;
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        initList(root, p, q);
//        return getIndex();
//    }
//
//    TreeNode getIndex(){
//        int index = list.size()/2;
//        int min = Math.min(pIndex, qIndex);
//        int max = Math.max(pIndex, qIndex);
//
//        if(min<index && index<max){
//            return list.get(index);
//        }else if(index < min){
//            return list.get(min);
//        }else {
//            return  list.get(max);
//        }
//    }
//
//    void initList(TreeNode root, TreeNode p, TreeNode q){
//        if(root==null){
//            return;
//        }
//        initList(root.left, p, q);
//        if(root.val == p.val){
//            pIndex = index;
//        }
//        if(root.val == qIndex){
//            qIndex = index;
//        }
//        list.add(index++, root);
//        initList(root.right, p, q);
//    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
